﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace 最长回文子串
{
    class Program
    {
        static void Main(string[] args)
        {

            string test = "装表涨白";
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            Solution solution = new Solution();
            Console.WriteLine(solution.LongestPalindrome(test));
            stopwatch.Stop();
            Console.WriteLine(stopwatch.ElapsedMilliseconds+"ms");
            Console.ReadLine();
        }

    }
    public class Solution
    {
        private SortedList<char, List<int>> dict = new SortedList<char, List<int>>();
        //private SortedDictionary<char, List<int>> dict = new SortedDictionary<char, List<int>>();
        //private Dictionary<char, List<int>> dict = new Dictionary<char, List<int>> ();
        public string LongestPalindrome(string s)
        {
            dict.Clear();
            int num = 0;
            string result = "";
            for (int i = 0; i < s.Length; i++)
            {
                if (dict.ContainsKey(s[i]))
                {
                    dict[s[i]].Add(i);
                }
                else
                {
                    List<int> l = new List<int>();
                    l.Add(i);
                    dict.Add(s[i],l);
                }
            }
            if (s.Length > 0)
            {
                result = s[0].ToString();
                foreach (var item in dict)
                {
                    if (item.Value.Count < 2)
                    {
                        continue;
                    }
                    else
                    {
                        for (int i = 0; i < item.Value.Count - 1; i++)
                        {
                            for (int j = item.Value.Count-1; j >= i; j--)
                            {
                                int dif = item.Value[j] - item.Value[i]+1;
                                string c = s.Substring(item.Value[i], dif);
                                if (Result(c))
                                {
                                    if (c.Length > num)
                                    {
                                        result = c;
                                        num = c.Length;
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }

            }
            return result;
        }
        //判断是否是回文子串
        public bool Result(string str)
        {
            string str1 = str;
            for (int i = 0; i < str.Length/2; i++)
            {
                if (str[i] != str1[str.Length - 1 - i])
                {
                    return false;
                }
            }
            return true;

        }
    }
}
